1. Field of the Invention
The present invention generally relates to decompressing compressed data at high speeds, and, more particularly, decompressing JPEG compressed image data at high speed for image reproduction by printers or displays.
2. Description of the Prior Art
Storage and transfer of data in digital form is becoming increasingly widespread at least because digital signals are less subject to noise, errors can often be corrected, archival storage media are more efficient and economical and electronic infrastructure for transmission and processing of digital data is widely available. However, some types of data, such as image data, when placed in digital form, often requires very large numbers of bytes of data to represent a single image; thus increasing the cost of storage medium or time of transmission which would be required to accommodate such a relatively massive amount of data.
As a solution to these problems, numerous data compression techniques have been developed in recent years. Notably, a technique has been developed by the Joint Photographic Experts Group (JPEG) which has become an industry standard for compression of image data. This technique provides substantial flexibility in controlling the size of the resulting compressed data and maximizes fidelity of a reconstructed image for a given degree of data compression. JPEG can be implemented in either hardware or software or a combination thereof. In general, since data processing for JPEG compression or decompression/reconstruction is relatively complex, special hardware was initially preferred and remains so for some particularly demanding applications such as high-speed printers or copiers or displays, although JPEG is currently more often implemented in software where speed is less critical. However, where speed is critical for image reproduction from compressed data, special purpose hardware remains preferred for decompression.
There are a number of software and hardware solutions that use very different algorithms to manage decompression, all resulting in more memory requirements and larger circuit counts. The first JPEG chip was produced by a startup company, C-Cube, in 1989 and was their stepping stone to MPEG hardware. C-Cube no longer supplies JPEG hardware. Several other JPEG chips previously offered have gone end-of-life and are, in any event, no longer capable of meeting current requirements for processing speed. Moreover, design of application specific integrated circuits (ASICs) capable of required decompression processing speeds is difficult and expensive since they would require a relatively large chip to provide sufficient memory and, since the number of applications requiring exceptional decompression processing speeds are relatively limited, such large ASICs are not considered to be economically feasible at the present time. As an alternative to ASICs, however, so-called field programmable gate arrays (FPGAs) of large size and increased speed have recently become available and FPGAs are available at marginally acceptable cost since they are fabricated in a generalized form that may be freely programmed and thus are applicable to a wide range of applications. such large and high clock speed FPGAs have been investigated for use in high speed image data decompression applications. FPGAs are essentially arrays of various logic gates which may be effectively connected together to perform a desired collective function in accordance with signals stored in a preferably non-volatile memory structure.
Unfortunately, it has been found that the processing for decoding JPEG Huffman codes (and corresponding codes using other compression techniques) could not be accomplished at the required speeds even at the increased clock rates available in current FPGAs. Moreover, the look-up tables used in the process of decoding such codes (which must be alterable) are generally very large and could not be accommodated by smaller and more economically feasible currently available FPGAs.